#include <vector>
#include <stdio.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() != vin.size()) return NULL;
        if(pre.size() == 0) return NULL;
        return BuildTree(pre.size(), &pre[0], &vin[0]);
    }

    int find(int val, int n, int* vin)
    {
        for(int i = 0; i < n; ++i)
        {
            if(vin[i] == val) return i;
        }
        return 0;
    }

    TreeNode* BuildTree(int n, int* pre, int* vin)
    {
        if(n == 0) return NULL;
        int val = pre[0];
        TreeNode* root = new TreeNode(val);
        int index = find(val, n, vin);
        TreeNode* left = BuildTree(index, pre+1, vin);
        TreeNode* right = BuildTree(n - index - 1, pre + index + 1, vin + index + 1);
        root->left = left;
        root->right = right;
        return root;
    }
};
// 前序输出测试
void PrePrint(TreeNode* root)
{
    if(root == NULL) return;
    printf("%d ", root->val);
    PrePrint(root->left);
    PrePrint(root->right);
}

int main()
{
    Solution s;
    // 普通测试
    vector<int> pre = {1,2,3};
    vector<int> vin = {2,1, 3};
    TreeNode* root = s.reConstructBinaryTree(pre, vin);
    PrePrint(root);
    printf("\n");
    pre = {1,2,4,7,3,5,6,8};
    vin = {4,7,2,1,5,3,8,6};
    root = s.reConstructBinaryTree(pre, vin);
    PrePrint(root);
    printf("\n");
    // 一个元素测试
    pre = {1};
    vin = {1};
    root = s.reConstructBinaryTree(pre, vin);
    PrePrint(root);
    printf("\n");
    // 只有左子树测试
    pre = {1, 2};
    vin = {2, 1};
    root = s.reConstructBinaryTree(pre, vin);
    PrePrint(root);
    printf("\n");

    // 只有右子树测试
    pre = {1,2};
    vin = {1,2};
    root = s.reConstructBinaryTree(pre, vin);
    PrePrint(root);
    printf("\n");

    // 没有元素测试
    pre = {};
    vin = {};
    root = s.reConstructBinaryTree(pre, vin);
    PrePrint(root);
    printf("\n");
    return 0;
}